package com.leetcode.test.stack;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 有效的括号  https://leetcode-cn.com/explore/learn/card/queue-stack/218/stack-last-in-first-out-data-structure/878/
 */
public class Bracket {

	@Test
	public void test() {
		Assert.assertTrue(isValid("()"));
		Assert.assertTrue(isValid("()[]{}"));
		Assert.assertFalse(isValid("(]"));
		Assert.assertFalse(isValid("([)]"));
		Assert.assertTrue(isValid("{[]}"));
	}

	private static boolean isValid(String string) {
		Stack<Character>          stack = new Stack<>();
		Map<Character, Character> map   = new HashMap<>();
		map.put('(', ')');
		map.put('{', '}');
		map.put('[', ']');

		for (int i = 0; i < string.length(); i++) {
			char c = string.charAt(i);

			if (stack.isEmpty()) {
				stack.push(c);
				continue;
			}

			char last = stack.peek();

			// 当前括号，对应栈最后一个括号，出栈
			if (map.containsKey(last) && c == map.get(last)) {
				stack.pop();
				continue;
			}

			stack.push(c);
		}

		return stack.isEmpty();
	}
}
